/*
 * Hyuga: A Density-Grid Stream Clustering Platform.
 * Copyright (C) 2014 PUC-Rio/Laboratory for Advanced Collaboration
 *
 * Hyuga is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * Hyuga is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with Hyuga.  If not, see <http://www.gnu.org/licenses/>.
 */
package br.pucrio.inf.lac.konoha.hyuga.datastructure;

/**
 * A Segment Tree data structure implementation using binary search and raw vectors.
 * 
 * The segments are directly represented by the vector entries, thus the following segment
 * 2 - 5 - 8 - 11 - 13 - 15 is represented by the array [2, 5, 8, 11, 13, 15].
 * Each segment index represent numbers from this value to the next value, e.g., the index 2 of the previous array
 * represent numbers from 8 (inclusive) to 11 (exclusive). For example, the segment that has the index of value 14 is 4,
 * since the 4th index represent numbers from 13 (inclusive) to 15 (exclusive). Finally, the segment that contains the
 * value 5 is 1, since the 1st index represent numbers from 5 (inclusive) to 8 (exclusive).    
 * 
 * @author Marcos Roriz <mroriz@inf.puc-rio.br>
 */
public class SegmentTree {
	
	/** Segments array */
	private double[] segments;

	/**
	 * An array containing a set of segment endpoints.
	 * @param segmentValues in a double array.
	 */
	public SegmentTree(double[] segmentValues) {
		if (segmentValues == null) throw new NullPointerException();
		
		boolean sorted  = true;
		String errorMSG = "";
		for (int i = 1; i < segmentValues.length; i++) {
			if (segmentValues[i-1] > segmentValues[i]) {
				sorted   = false;
				errorMSG = segmentValues[i-1] + ">" + segmentValues[i];
				break;
			}
		}

		if (!sorted) throw new IllegalArgumentException("Segment vector is not sorted. " + errorMSG);
		this.segments = segmentValues;
	}
	
	/**
	 * Find the segment index that contains this value.
	 * 
	 * In this implementation we are using a basic binary search in the segment vector.
	 * 
	 * @param value a specific number.
	 * @throws IndexOutOfBoundsException if the value is not in the segment vector.
	 * 
	 * @return a segment index that contains a range with this number.
	 */
	public int findIndex(double value) throws IndexOutOfBoundsException {
		if (segments == null)					   throw new NullPointerException();
		if (value < segments[0])                   throw new IndexOutOfBoundsException();
		if (value > segments[segments.length - 1]) throw new IndexOutOfBoundsException();
		
		int lowerBound  = 0;
		int higherBound = segments.length;
		int median      = (lowerBound + higherBound) / 2;
		
		do {
			if      (value < segments[median]) higherBound = median - 1;
			else if (value > segments[median]) lowerBound  = median + 1;
			else {
				higherBound = median;
				lowerBound  = median;
				break;
			}
			
			median = (lowerBound + higherBound) / 2;
		} while (lowerBound < higherBound);

		lowerBound 	= Math.max(0, 					lowerBound  - 2);
		higherBound = Math.min(segments.length - 1, higherBound + 2);
		int index 	= lowerBound;
		
		for (index = 1; index <= higherBound; index++) {
			if (value < segments[index]) {
				break;
			}
		}
		
		return Math.max(0, index - 1);
	}
	
	/**
	 * Returns the segments.
	 * 
	 * @return segments vector.
	 */
	public double[] getSegments() {
		return segments;
	}
}
